package com.maishi.programmer.jainzhioffer;

import java.util.Stack;

/**
 * Created by brossdong on 2018/3/31.
 * 定义栈的数据结构，请在该类型中实现一个能够得到栈最小元素的min函数。
 * 时间复杂度O(1)
 */
public class TestProblem30 {

    Stack<Integer> stack = new Stack();
    Stack<Integer> stackmin = new Stack();
    //记录最小数
    Integer num = null;
    public void push(int node) {
        if (num == null) {
            num = node;
            stack.push(node);
            stackmin.push(num);
        } else {
            if (node <= num) {
                num = node;
                stackmin.push(num);
            }
            stack.push(node);
        }
    }

    public void pop() {
        Integer pop1 = stack.pop();
        Integer pop2 = stackmin.pop();
        if (pop1 != pop2) {
            stackmin.push(pop2);
        }
    }

    public int top() {
        Integer top = stack.pop();
        stack.push(top);
        return top;
    }

    public int min() {
        Integer top = stackmin.pop();
        stackmin.push(top);
        return top;
    }

    public static void main(String[] args) throws ClassNotFoundException {
        TestProblem30 test = new TestProblem30();
        Class<?> aClass = Class.forName("com.maishi.programmer.jainzhioffer.TestProblem30");
        System.out.println(aClass);
        test.push(1);
        test.push(3);
        test.push(5);
        test.push(1);
        test.push(9);
        test.push(6);
        int min = test.min();
        System.out.println(min);
    }

}
